Ruthenium catalysts are well known to possess unique efficacy for the catalytic removal of NO.sub.x from the exhaust gases of internal combustion engine and stationary sources while avoiding the production of ammonia. However, a principal drawback to their practical utilization is the tendency of ruthenium to form volatile oxides (RuO.sub.3 and RuO.sub.4) at high temperatures in the presence of oxygen and/or steam. Such volatilization losses result in large catalytic NO.sub.x removal variations. This tendency is particularly unfortunate in light of the fact that under normal operating conditions, internal combustion engines produce very high temperatures and continuously varying oxygen content gases, depending upon the fuel/air ratio being delivered by the standard carburetor to meet load requirements. Stationary sources tend to produce lean effluent waste streams. Therefore, for any catalyst system used to reduce NO.sub.x to be realistically attractive, it must be characterized by a high and sustained activity, coupled with physical and chemical ruggedness, and pronounced resistance to ruthenium oxide volatilization.